{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closest Subsequence Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #two-pointers #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #双指针 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minAbsDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最接近目标值的子序列和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个目标值 <code>goal</code> 。</p>\n",
    "\n",
    "<p>你需要从 <code>nums</code> 中选出一个子序列，使子序列元素总和最接近 <code>goal</code> 。也就是说，如果子序列元素和为 <code>sum</code> ，你需要 <strong>最小化绝对差</strong> <code>abs(sum - goal)</code> 。</p>\n",
    "\n",
    "<p>返回 <code>abs(sum - goal)</code> 可能的 <strong>最小值</strong> 。</p>\n",
    "\n",
    "<p>注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [5,-7,3,5], goal = 6\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>选择整个数组作为选出的子序列，元素和为 6 。\n",
    "子序列和与目标值相等，所以绝对差为 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [7,-9,15,-2], goal = -5\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>选出子序列 [7,-9,-2] ，元素和为 -4 。\n",
    "绝对差为 abs(-4 - (-5)) = abs(1) = 1 ，是可能的最小值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3], goal = -7\n",
    "<strong>输出：</strong>7\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 40</code></li>\n",
    "\t<li><code>-10<sup>7</sup> &lt;= nums[i] &lt;= 10<sup>7</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= goal &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closest-subsequence-sum](https://leetcode.cn/problems/closest-subsequence-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closest-subsequence-sum](https://leetcode.cn/problems/closest-subsequence-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,-7,3,5]\\n6', '[7,-9,15,-2]\\n-5', '[1,2,3]\\n-7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        n1, n2 = n // 3, n * 2 // 3\n",
    "\n",
    "        def sub(arr):\n",
    "            s = {0}\n",
    "            if arr:\n",
    "                M = 1 << len(arr)\n",
    "                tot = [0] * M\n",
    "                for mask in range(1, M):\n",
    "                    tot[mask] = tot[mask & (mask - 1)] + arr[(mask & (-mask)).bit_length() - 1]\n",
    "                    s.add(tot[mask])\n",
    "            return sorted(s)\n",
    "\n",
    "        s1, s2, s3 = sub(nums[:n1]), sub(nums[n1:n2]), sub(nums[n2:])\n",
    "        ans = float('inf')\n",
    "        for x in s1:\n",
    "            l, r = 0, min(bisect.bisect_right(s3, goal - s2[0] - x), len(s3) - 1)\n",
    "            m, g = len(s2), goal - x\n",
    "            while l < m and r >= 0:\n",
    "                v = s2[l] + s3[r] - g\n",
    "                if v == 0:\n",
    "                    return 0\n",
    "                if v > 0:\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "                    v = -v\n",
    "                if v < ans:\n",
    "                    ans = v\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        st1, st2 = set([0]), set([0])\n",
    "        for x in nums:\n",
    "            if x == 0: continue\n",
    "            st = st1 if len(st1) <= len(st2) else st2\n",
    "            for s in list(st): st.add(s + x)\n",
    "        a, b = sorted(st1), sorted(st2)\n",
    "        m, n = len(a), len(b)\n",
    "        res = inf\n",
    "        for x in a:\n",
    "            i = bisect_left(b, goal - x)\n",
    "            if i < n: res = min(res, x + b[i] - goal)\n",
    "            if i: res = min(res, goal - (x + b[i - 1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        s1, s2 = set([0]), set([0])\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                continue\n",
    "            st = s1 if len(s1) <= len(s2) else s2\n",
    "            for s in list(st):\n",
    "                st.add(s + x)\n",
    "\n",
    "        s1, s2 = sorted(s1), sorted(s2)\n",
    "        ans = abs(goal)\n",
    "        l, r = 0, len(s2) - 1\n",
    "        while ans and l < len(s1) and r >= 0:\n",
    "            t = s1[l] + s2[r]\n",
    "            ans = min(ans, abs(goal - t))\n",
    "            if t > goal:\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        s1, s2 = set([0]), set([0])\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                continue\n",
    "            s = s1 if len(s1) <= len(s2) else s2\n",
    "            for x in list(s):\n",
    "                s.add(x + num)\n",
    "\n",
    "        s1, s2 = sorted(s1), sorted(s2)\n",
    "        ans = abs(goal)\n",
    "\n",
    "        l, r = 0, len(s2) - 1\n",
    "        while l < len(s1) and r >= 0:\n",
    "            t = s1[l] + s2[r]\n",
    "            ans = min(ans, abs(goal - t))\n",
    "            if t > goal:\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        s1, s2 = set([0]), set([0])\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                continue\n",
    "            s = s1 if len(s1) <= len(s2) else s2\n",
    "            for x in list(s):\n",
    "                s.add(x + num)\n",
    "\n",
    "        s1, s2 = sorted(s1), sorted(s2)\n",
    "        ans = abs(goal)\n",
    "\n",
    "        # l, r = 0, len(s2) - 1\n",
    "        # while ans and l < len(s1) and r >= 0:\n",
    "        #     t = s1[l] + s2[r]\n",
    "        #     ans = min(ans, abs(goal - t))\n",
    "        #     if t > goal:\n",
    "        #         r -= 1\n",
    "        #     else:\n",
    "        #         l += 1\n",
    "        \n",
    "        for x in s1:\n",
    "            t = goal - x\n",
    "            idx = bisect_left(s2, t)\n",
    "            for i in (idx - 1, idx):\n",
    "                if 0 <= i < len(s2):\n",
    "                    ans = min(ans, abs(t - s2[i]))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        h = len(nums)//2\n",
    "        l = set()\n",
    "        for m in range(0,1<<h):\n",
    "            acc = 0\n",
    "            for i in range(h):\n",
    "                if m >> i & 1:\n",
    "                    acc += nums[i]\n",
    "            l.add(acc)\n",
    "        l = list(l)\n",
    "        l.sort()\n",
    "\n",
    "        f = len(nums) - h\n",
    "        ans = inf\n",
    "        for m in range(0,1<<f):\n",
    "            acc = 0\n",
    "            for i in range(f):\n",
    "                if m >> i & 1:\n",
    "                    acc += nums[i+h]\n",
    "            \n",
    "            p = bisect_right(l, goal - acc)\n",
    "            if p != len(l):\n",
    "                ans = min(abs(goal - acc - l[p]), ans)\n",
    "            if p - 1 >= 0:\n",
    "                ans = min(abs(goal - acc - l[p-1]),ans)\n",
    "\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        half = n // 2\n",
    "        ls, rs = half, n - half\n",
    "        lsum = [0] * (1 << ls)\n",
    "        for i in range(1, 1 << ls):\n",
    "            for j in range(ls):\n",
    "                if i & (1 << j) == 0:\n",
    "                    continue\n",
    "                lsum[i] = lsum[i - (1 << j)] + nums[j]\n",
    "                break\n",
    "        rsum = [0] * (1 << rs)\n",
    "        for i in range(1, 1 << rs):\n",
    "            for j in range(rs):\n",
    "                if i & (1 << j) == 0:\n",
    "                    continue\n",
    "                rsum[i] = rsum[i - (1 << j)] + nums[j + ls]\n",
    "                break\n",
    "        \n",
    "        lsum.sort()\n",
    "        rsum.sort()\n",
    "        ans = float('inf')\n",
    "        for total in lsum:\n",
    "            ans = min(ans, abs(total - goal))\n",
    "        for total in rsum:\n",
    "            ans = min(ans, abs(total - goal))\n",
    "        i, j = 0, (1 << rs) - 1\n",
    "        while i < (1 << ls) and j >= 0:\n",
    "            total = lsum[i] + rsum[j]\n",
    "            ans = min(ans, abs(total - goal))\n",
    "            if total > goal:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        mid = n // 2\n",
    "        ls, rs = mid, n - mid\n",
    "\n",
    "        lsum = [0] * (1 << ls)\n",
    "        for i in range(1, 1<<ls):\n",
    "            for j in range(ls):\n",
    "                if (i & (1 << j)) == 0: continue\n",
    "                lsum[i] = lsum[i-(1<<j)] + nums[j]\n",
    "                break\n",
    "        rsum = [0] * (1 << rs)\n",
    "        for i in range(1, 1<<rs):\n",
    "            for j in range(rs):\n",
    "                if (i & (1 << j)) == 0: continue\n",
    "                rsum[i] = rsum[i-(1<<j)] + nums[ls + j]\n",
    "                break\n",
    "        \n",
    "        lsum.sort()\n",
    "        rsum.sort()\n",
    "\n",
    "        ans = inf\n",
    "        for x in lsum: ans = min(ans, abs(goal-x))\n",
    "        for x in rsum: ans = min(ans, abs(goal-x))\n",
    "        i, j = 0, len(rsum) - 1\n",
    "        while i < len(lsum) and j >= 0:\n",
    "            s = lsum[i] + rsum[j]\n",
    "            ans = min(ans, abs(goal-s))\n",
    "            if s > goal: j -= 1\n",
    "            else: i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        ln = n // 2\n",
    "        rn = n - ln\n",
    "        lsum = [0] * (1 << ln)\n",
    "        rsum = [0] * (1 << rn)\n",
    "        for mask in range(1 << ln):\n",
    "            for idx in range(ln):\n",
    "                if mask & 1 << idx:\n",
    "                    lsum[mask] = lsum[mask - (1 << idx)] + nums[idx]\n",
    "                    break\n",
    "\n",
    "        for mask in range(1 << rn):\n",
    "            for idx in range(rn):\n",
    "                if mask & 1 << idx:\n",
    "                    rsum[mask] = rsum[mask - (1 << idx)] + nums[idx + ln]\n",
    "                    break\n",
    "\n",
    "        lsum.sort()\n",
    "        rsum.sort()\n",
    "        res = (2 << 63) - 1\n",
    "        for item in lsum:\n",
    "            res = min(res, abs(item - goal))\n",
    "        for item in rsum:\n",
    "            res = min(res, abs(item - goal))\n",
    "        # print(f\"lsum: {lsum}\")\n",
    "        # print(f\"rsum: {rsum}\")\n",
    "        # print(res)\n",
    "        left, right = 0, len(rsum) - 1\n",
    "        while left < len(lsum) and right >= 0:\n",
    "            tmp = lsum[left] + rsum[right]\n",
    "            res = min(res, abs(tmp - goal))\n",
    "            # print(f\"left:{left}, right: {right}, tmp:{tmp},res: {res}\")\n",
    "            if tmp - goal > 0:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fill = 0\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        global fill\n",
    "        n = len(nums)\n",
    "        max1 = 0\n",
    "        min1 = 0\n",
    "        lsums = []\n",
    "        rsums = []\n",
    "        ans = 10000000\n",
    "        for i in range(n):\n",
    "            if nums[i] >= 0:\n",
    "                max1 += nums[i]\n",
    "            else:\n",
    "                min1 += nums[i]\n",
    "        if max1 < goal:\n",
    "            return goal - max1\n",
    "        if min1 > goal:\n",
    "            return min1 - goal\n",
    "        nums.sort()\n",
    "        def collect(i, e, s, sums):\n",
    "            global fill\n",
    "            if i == e:\n",
    "                sums.append(s)\n",
    "                fill += 1\n",
    "            else:\n",
    "                j = i + 1\n",
    "                while j < e and nums[j] == nums[i]:\n",
    "                    j += 1\n",
    "                for k in range(j-i+1):\n",
    "                    collect(j, e, s + k * nums[i], sums)\n",
    "        collect(0, n // 2, 0, lsums)\n",
    "        lsize = fill\n",
    "        fill = 0\n",
    "        collect(n // 2, n, 0, rsums)\n",
    "        rsize = fill\n",
    "        lsums.sort()\n",
    "        rsums.sort()\n",
    "        r = len(rsums) - 1\n",
    "        for l in range(len(lsums)):\n",
    "            while r > 0 and abs(goal - rsums[r] - lsums[l]) >= abs(goal - rsums[r-1] - lsums[l]):\n",
    "                r -= 1\n",
    "            ans = min(ans, abs(goal - rsums[r] - lsums[l]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        max_sum = 0\n",
    "        min_sum = 0\n",
    "        for x in nums:\n",
    "            if x > 0:\n",
    "                max_sum += x\n",
    "            else:\n",
    "                min_sum +=x\n",
    "        if max_sum < goal:\n",
    "            return goal - max_sum\n",
    "        if min_sum > goal:\n",
    "            return min_sum - goal\n",
    "        res1 = []\n",
    "        res2 = []\n",
    "        def dfs(nums, i, s, k, res):\n",
    "            if i == k:\n",
    "                res.append(s)\n",
    "                return\n",
    "            j = i + 1\n",
    "            while j < k and nums[j] == nums[i]:\n",
    "                j += 1\n",
    "            for c in range(j - i + 1):\n",
    "                dfs(nums, j, s + nums[i] * c, k, res)\n",
    "        dfs(nums[0:n // 2], 0, 0, n // 2, res1)\n",
    "        dfs(nums, n // 2, 0, n, res2)\n",
    "        m, n = len(res1), len(res2)\n",
    "        res1.sort()\n",
    "        res2.sort()\n",
    "        i = 0\n",
    "        j = n - 1\n",
    "        ans = inf\n",
    "        while i < m:\n",
    "            while j > 0 and abs(goal - res1[i] - res2[j - 1]) <= abs(goal - res1[i] - res2[j]):\n",
    "                j -= 1\n",
    "            ans = min(ans, abs(goal - res1[i] - res2[j]))\n",
    "            i += 1\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fill = 0\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        global fill\n",
    "        n = len(nums)\n",
    "        max1 = 0\n",
    "        min1 = 0\n",
    "        lsums = []\n",
    "        rsums = []\n",
    "        ans = 10000000\n",
    "        for i in range(n):\n",
    "            if nums[i] >= 0:\n",
    "                max1 += nums[i]\n",
    "            else:\n",
    "                min1 += nums[i]\n",
    "        if max1 < goal:\n",
    "            return goal - max1\n",
    "        if min1 > goal:\n",
    "            return min1 - goal\n",
    "        nums.sort()\n",
    "        def collect(i, e, s, sums):\n",
    "            global fill\n",
    "            if i == e:\n",
    "                sums.append(s)\n",
    "                fill += 1\n",
    "            else:\n",
    "                j = i + 1\n",
    "                while j < e and nums[j] == nums[i]:\n",
    "                    j += 1\n",
    "                for k in range(j-i+1):\n",
    "                    collect(j, e, s + k * nums[i], sums)\n",
    "        collect(0, n // 2, 0, lsums)\n",
    "        lsize = fill\n",
    "        fill = 0\n",
    "        collect(n // 2, n, 0, rsums)\n",
    "        rsize = fill\n",
    "        lsums.sort()\n",
    "        rsums.sort()\n",
    "        r = len(rsums) - 1\n",
    "        for l in range(len(lsums)):\n",
    "            while r > 0 and abs(goal - rsums[r] - lsums[l]) >= abs(goal - rsums[r-1] - lsums[l]):\n",
    "                r -= 1\n",
    "            ans = min(ans, abs(goal - rsums[r] - lsums[l]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums, goal):\n",
    "        lsum = []\n",
    "        rsum = []\n",
    "\n",
    "        def collect(nums, i, e, s, _sum):\n",
    "            if i == e:\n",
    "                _sum.append(s)\n",
    "            else:\n",
    "                j = i + 1\n",
    "                while j < e and nums[j] == nums[i]:\n",
    "                    j += 1\n",
    "                for k in range(j - i + 1):\n",
    "                    collect(nums, j, e, s + k * nums[i], _sum)\n",
    "\n",
    "        n = len(nums)\n",
    "        min_val, max_val = 0, 0\n",
    "        for num in nums:\n",
    "            if num >= 0:\n",
    "                max_val += num\n",
    "            else:\n",
    "                min_val += num\n",
    "\n",
    "        if max_val < goal:\n",
    "            return abs(max_val - goal)\n",
    "        if min_val > goal:\n",
    "            return abs(min_val - goal)\n",
    "\n",
    "        nums.sort()\n",
    "        collect(nums, 0, n // 2, 0, lsum)\n",
    "        lsum.sort()\n",
    "\n",
    "        rsum.clear()\n",
    "        collect(nums, n // 2, n, 0, rsum)\n",
    "        rsum.sort()\n",
    "\n",
    "        ans = abs(goal)\n",
    "\n",
    "        i, j = 0, len(rsum) - 1\n",
    "        while i < len(lsum):\n",
    "            while j > 0 and abs(goal - lsum[i] - rsum[j - 1]) <= abs(goal - lsum[i] - rsum[j]):\n",
    "                j -= 1\n",
    "            ans = min(ans, abs(goal - lsum[i] - rsum[j]))\n",
    "            i += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "# Example usage:\n",
    "solution = Solution()\n",
    "nums = [1, 2, 3]\n",
    "goal = -7\n",
    "result = solution.minAbsDifference(nums, goal)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        half = n >> 1\n",
    "        left, right = nums[:half], nums[half:]\n",
    "        # print(left, right)\n",
    "\n",
    "        def get(part):\n",
    "            n = len(part)\n",
    "            cur = [0 for _ in range(1 << n)]\n",
    "            for state in range(1 << n):\n",
    "                for i in range(n):\n",
    "                    if (state >> i) & 1:\n",
    "                        cur[state] = part[i] + cur[state ^ (1 << i)]\n",
    "                        break\n",
    "            return cur\n",
    "\n",
    "        l, r = get(left), get(right)\n",
    "        l.sort() # 从小到大\n",
    "        r.sort(reverse=True) # 从大到小\n",
    "        # print(l, r)\n",
    "        ans = inf\n",
    "\n",
    "        index1, index2 = 0, 0\n",
    "        while index1 < len(l) and index2 < len(r):\n",
    "            cur = l[index1] + r[index2]\n",
    "            ans = min(ans, abs(cur - goal))\n",
    "            if goal < cur:\n",
    "                index2 += 1\n",
    "            elif goal > cur:\n",
    "                index1 += 1\n",
    "            else:\n",
    "                return 0\n",
    "                \n",
    "        while index1 < len(l):\n",
    "            ans = min(ans, abs(l[index1] + r[-1] - goal))\n",
    "            index1 += 1\n",
    "        while index2 < len(r):\n",
    "            ans = min(ans, abs(l[-1] + r[index2] - goal))\n",
    "            index2 += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        # 拆成两半考虑\n",
    "        n = len(nums)\n",
    "        half = n >> 1\n",
    "        left, right = nums[:half], nums[half:]\n",
    "\n",
    "        def get(part):\n",
    "            n = len(part)\n",
    "            cur = [0 for _ in range(1 << n)]\n",
    "            for state in range(1 << n):\n",
    "                for i in range(n):\n",
    "                    if (state >> i) & 1:\n",
    "                        cur[state] = part[i] + cur[state ^ (1 << i)]\n",
    "                        break\n",
    "            return cur\n",
    "\n",
    "        l, r = get(left), get(right)\n",
    "        # 双指针排序 找到最接近goal的最小值\n",
    "        l.sort() # 从小到大\n",
    "        r.sort(reverse=True) # 从大到小\n",
    "        # print(l, r)\n",
    "        ans = inf\n",
    "\n",
    "        index1, index2 = 0, 0\n",
    "        while index1 < len(l) and index2 < len(r):\n",
    "            cur = l[index1] + r[index2]\n",
    "            ans = min(ans, abs(cur - goal))\n",
    "            if goal < cur:\n",
    "                index2 += 1\n",
    "            elif goal > cur:\n",
    "                index1 += 1\n",
    "            else:\n",
    "                return 0\n",
    "                \n",
    "        # while index1 < len(l):\n",
    "        #     ans = min(ans, abs(l[index1] + r[-1] - goal))\n",
    "        #     index1 += 1\n",
    "        # while index2 < len(r):\n",
    "        #     ans = min(ans, abs(l[-1] + r[index2] - goal))\n",
    "        #     index2 += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        arr1=[0]\n",
    "        arr2=[0]\n",
    "        m=len(nums)\n",
    "        length1=1\n",
    "        for i in range(0,m//2):\n",
    "            for j in range(0,length1):\n",
    "                arr1.append(nums[i]+arr1[j])\n",
    "                length1+=1\n",
    "        length2=1\n",
    "        for i in range(m//2,m):\n",
    "            for j in range(0,length2):\n",
    "                arr2.append(nums[i]+arr2[j])\n",
    "                length2+=1\n",
    "        arr1.sort()\n",
    "        arr2.sort()\n",
    "        Min=abs(goal)\n",
    "        i=0\n",
    "        j=length2-1\n",
    "        while i < length1 and j >= 0:\n",
    "            ans=arr1[i]+arr2[j]\n",
    "            Min=min(Min,abs(goal-ans))\n",
    "            if ans > goal:\n",
    "                j-=1\n",
    "            elif ans < goal:\n",
    "                i+=1\n",
    "            else:\n",
    "                return 0\n",
    "        return Min\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        arr1 = [0]\n",
    "        arr2 = [0]\n",
    "        n = len(nums)\n",
    "        len1 = 1\n",
    "        for i in range(0, n//2):\n",
    "            for j in range(0, len1):\n",
    "                arr1.append(nums[i] + arr1[j])\n",
    "                len1 += 1\n",
    "        len2 = 1\n",
    "        for i in range(n//2, n):\n",
    "            for j in range(0, len2):\n",
    "                arr2.append(nums[i] + arr2[j])\n",
    "                len2 += 1\n",
    "        arr1.sort()\n",
    "        arr2.sort()\n",
    "        ans = abs(goal)\n",
    "        i, j = 0, len2-1\n",
    "        while i < len1 and j >= 0:\n",
    "            temp = arr1[i] + arr2[j]\n",
    "            ans = min(ans, abs(goal - temp))\n",
    "            if temp > goal:\n",
    "                j -= 1\n",
    "            elif temp < goal:\n",
    "                i += 1\n",
    "            else:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        pre = nums[:n // 2]\n",
    "        after = nums[n // 2:]\n",
    "\n",
    "        def get_all(arr):\n",
    "            res = []\n",
    "            m = len(arr)\n",
    "            for i in range(1 << m):\n",
    "                cur = 0\n",
    "                for j in range(m):\n",
    "                    if i & 1 << j:\n",
    "                        cur += arr[j]\n",
    "                res.append(cur)\n",
    "            return res\n",
    "\n",
    "        pret = get_all(pre)\n",
    "        aftert = get_all(after)\n",
    "        pret.sort()\n",
    "        aftert.sort()\n",
    "        j = len(aftert) - 1\n",
    "        ans = abs(goal)\n",
    "        # print(pret, aftert)\n",
    "        for i in range(len(pret)):\n",
    "            while j >= 0 and pret[i] + aftert[j] >= goal:\n",
    "                ans = min(ans, abs(pret[i] + aftert[j] - goal))\n",
    "                if ans == 0:\n",
    "                    return ans\n",
    "                j -= 1\n",
    "            if j >= 0:\n",
    "                ans = min(ans, abs(pret[i] + aftert[j] - goal))\n",
    "            if ans == 0:\n",
    "                return ans\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        half = n // 2\n",
    "\n",
    "        # 计算一个数组的所有可能的子序列和\n",
    "        def all_sums(arr: List[int]) -> List[int]:\n",
    "            res = [0]\n",
    "            for num in arr:\n",
    "                res += [x + num for x in res]\n",
    "            return res\n",
    "\n",
    "        # 计算两个子数组的所有可能的子序列和\n",
    "        left_sums = all_sums(nums[:half])\n",
    "        right_sums = all_sums(nums[half:])\n",
    "\n",
    "        # 对其中一个子数组的子序列和进行排序\n",
    "        right_sums.sort()\n",
    "\n",
    "        # 初始化最小的绝对差\n",
    "        min_diff = abs(goal)\n",
    "\n",
    "        # 使用二分查找找出最接近 goal 的子序列和\n",
    "        for left_sum in left_sums:\n",
    "            idx = bisect_left(right_sums, goal - left_sum)\n",
    "            if idx < len(right_sums):\n",
    "                min_diff = min(min_diff, abs(goal - (left_sum + right_sums[idx])))\n",
    "            if idx > 0:\n",
    "                min_diff = min(min_diff, abs(goal - (left_sum + right_sums[idx - 1])))\n",
    "\n",
    "        return min_diff\n",
    "\n",
    "# 示例\n",
    "nums = [5, -7, 3, 5]\n",
    "goal = 6\n",
    "sol = Solution()\n",
    "print(sol.minAbsDifference(nums, goal))  # 输出应该是 0，因为可以通过选择 [5, 1] 得到和为 6\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        a = set()\n",
    "        def dfs1(u, v):\n",
    "            if u == n // 2:\n",
    "                a.add(v)\n",
    "                return \n",
    "            \n",
    "            dfs1(u+1, v+nums[u])\n",
    "            dfs1(u+1, v)\n",
    "        \n",
    "        dfs1(0, 0)\n",
    "        a = sorted(list(a))\n",
    "        res = inf\n",
    "        def dfs2(u, v):\n",
    "            nonlocal res\n",
    "            if u == n:\n",
    "                pos = bisect_left(a, goal - v)\n",
    "                val = inf\n",
    "                if pos < len(a): val = abs(v+a[pos] - goal)\n",
    "                if pos > 0: val = min(val, abs(v+a[pos-1] - goal))\n",
    "                res = min(res, val)\n",
    "                return \n",
    "            dfs2(u+1, v+nums[u])\n",
    "            dfs2(u+1, v)\n",
    "        \n",
    "        dfs2(n//2, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        half = n >> 1\n",
    "        \n",
    "        \n",
    "        s = nums[:half]\n",
    "        k = half\n",
    "        cand = []\n",
    "        def go(idx, v):\n",
    "            if idx == k:\n",
    "                cand.append(v)\n",
    "                return\n",
    "            go(idx + 1, v)\n",
    "            go(idx + 1, v + s[idx])\n",
    "        go(0, 0)\n",
    "        cand.sort()\n",
    "        \n",
    "        s = nums[half:]\n",
    "        k = n - half\n",
    "        ret = 2 * 10 ** 9\n",
    "        n = len(cand)\n",
    "        def go2(idx, v):\n",
    "            if idx == k:\n",
    "                nonlocal ret\n",
    "                t = goal - v\n",
    "                l, r = 0, n - 1\n",
    "                while l <= r:\n",
    "                    m = l + r >> 1\n",
    "                    if cand[m] >= t:\n",
    "                        r = m - 1\n",
    "                    else:\n",
    "                        l = m + 1\n",
    "                if r >= 0:\n",
    "                    if t - cand[r] < ret:\n",
    "                        ret = t - cand[r]\n",
    "                if r + 1 < n:\n",
    "                    if cand[r + 1] - t < ret:\n",
    "                        ret = cand[r + 1] - t\n",
    "                return\n",
    "            go2(idx + 1, v)\n",
    "            go2(idx + 1, v + s[idx])\n",
    "        go2(0, 0)\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = set()\n",
    "\n",
    "        def dfs1(i, c, s):\n",
    "            if i == n // 2:\n",
    "                m.add(s)\n",
    "                return\n",
    "            dfs1(i + 1, c + 1, s + nums[i])\n",
    "            dfs1(i + 1, c, s)\n",
    "    \n",
    "        ss = sum(nums) \n",
    "        dfs1(0, 0, 0)\n",
    "        m = sorted(list(m))\n",
    "        minl = inf\n",
    "        def dfs2(i, c, s):\n",
    "            if i == n:\n",
    "                nonlocal minl\n",
    "                idx = bisect_right(m, goal - s)\n",
    "                if idx < len(m): \n",
    "                    s1 = m[idx]\n",
    "                    minl = min(minl, abs(goal - s1 - s))\n",
    "                if idx - 1 >= 0:\n",
    "                    s1 = m[idx - 1]\n",
    "                    minl = min(minl, abs(goal - s1 - s))\n",
    "                return\n",
    "            dfs2(i + 1, c + 1, s + nums[i])\n",
    "            dfs2(i + 1, c, s)\n",
    "        \n",
    "        dfs2(n // 2, 0, 0)\n",
    "        return minl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        # def subset_sum(s, e):\n",
    "        #     a = e - s + 1\n",
    "        #     b = 1 << a\n",
    "        #     sums = [0] * b\n",
    "        #     # print(a, b)\n",
    "        #     for i in range(1, b):\n",
    "        #         for j in range(a-1, -1, -1):\n",
    "        #             t = 1 << j\n",
    "        #             if t & i:\n",
    "        #                 sums[i] = nums[s+j] + sums[i - t]\n",
    "        #                 break\n",
    "            \n",
    "        #     return sums\n",
    "\n",
    "        def subset_sum(arrs):\n",
    "            res = [0]\n",
    "            for num0 in arrs:\n",
    "                tmp = []\n",
    "                for num1 in res:\n",
    "                    tmp.append(num0 + num1)\n",
    "                res.extend(tmp)\n",
    "            \n",
    "            return res\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        # left = subset_sum(0, m)\n",
    "        left = subset_sum(nums[:m])\n",
    "        if goal in set(left):\n",
    "            return 0\n",
    "        # right = subset_sum(m+1, n-1)\n",
    "        right = subset_sum(nums[m:])\n",
    "        if goal in set(right):\n",
    "            return 0\n",
    "        \n",
    "        left.sort()\n",
    "        right.sort()\n",
    "        i = 0\n",
    "        sz = len(left)\n",
    "        j = len(right) - 1\n",
    "\n",
    "        ans = int(1e9)\n",
    "        while i < sz and j >= 0:\n",
    "            t = left[i] + right[j]\n",
    "            ans = min(ans, abs(t-goal))\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "            if t > goal:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, a: List[int], g: int) -> int:\n",
    "        n = len(a)\n",
    "        if n==1:\n",
    "            return min(abs(g), abs(g - a[0])) \n",
    "        else:\n",
    "            t = n//2 \n",
    "            b = a[:t]\n",
    "            c = a[t:]\n",
    "            def f(x):\n",
    "                if not x:\n",
    "                    return [0] \n",
    "                else:\n",
    "                    t = x.pop()\n",
    "                    ans = f(x)\n",
    "                    for j in range(len(ans)):\n",
    "                        ans.append(t + ans[j])\n",
    "                    return ans \n",
    "            b = f(b)\n",
    "            c = sorted(f(c))\n",
    "            ans = float('inf')\n",
    "            for j in b:\n",
    "                tmp = g - j\n",
    "                i = bisect_left(c, tmp) \n",
    "                left = max(i-1, 0)\n",
    "                right = min(len(c)-1, i)\n",
    "                l = c[left] + j - g \n",
    "                r = c[right] + j - g \n",
    "                ans = min([ans, abs(l), abs(r)]) \n",
    "            return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "        def minAbsDifference(self, nums: List[int], goal: int) -> int:\r\n",
    "            ans=float('inf') ###### 初始化\r\n",
    "\r\n",
    "            def flat(array,pos,flat_array):\r\n",
    "                '''\r\n",
    "                param..\r\n",
    "                array: 原数组\r\n",
    "                pos  当前位置\r\n",
    "                flat_array : 当前枚举数组的结果\r\n",
    "                '''\r\n",
    "                if pos>len(array)-1:\r\n",
    "                    return flat_array\r\n",
    "                temp=flat_array+[ele+array[pos] for ele in flat_array]\r\n",
    "                return flat(array,pos+1,temp)\r\n",
    "            \r\n",
    "            mid=(len(nums))//2 ### 取一半\r\n",
    "            left=flat(nums[:mid],0,[0])  #### 初始应加入 [0] 作为不选元素时候的子序列总和\r\n",
    "            right=flat(nums[mid:],0,[0])\r\n",
    "\r\n",
    "            left=sorted(left)\r\n",
    "            right=sorted(right,reverse=True)\r\n",
    "            left_id=0\r\n",
    "            right_id=0\r\n",
    "\r\n",
    "            ####### 双指针\r\n",
    "            while(left_id<len(left) and right_id<len(right)):\r\n",
    "                cur=left[left_id]+right[right_id]\r\n",
    "                ans=min(abs(cur-goal),ans)\r\n",
    "                if cur>goal:\r\n",
    "                    right_id+=1\r\n",
    "                elif cur<goal:\r\n",
    "                    left_id+=1\r\n",
    "                else:\r\n",
    "                    return 0\r\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        half = n >> 1\n",
    "        \n",
    "        \n",
    "        s = nums[half:]\n",
    "        k = n - half\n",
    "        cand = []\n",
    "        def go(idx, v):\n",
    "            if idx == k:\n",
    "                cand.append(v)\n",
    "                return\n",
    "            go(idx + 1, v)\n",
    "            go(idx + 1, v + s[idx])\n",
    "        go(0, 0)\n",
    "        cand.sort()\n",
    "        \n",
    "        s = nums[:half]\n",
    "        k = half\n",
    "        ret = 2 * 10 ** 9\n",
    "        n = len(cand)\n",
    "        def go2(idx, v):\n",
    "            if idx == k:\n",
    "                nonlocal ret\n",
    "                t = goal - v\n",
    "                l, r = 0, n - 1\n",
    "                while l <= r:\n",
    "                    m = l + r >> 1\n",
    "                    if cand[m] >= t:\n",
    "                        r = m - 1\n",
    "                    else:\n",
    "                        l = m + 1\n",
    "                if r >= 0:\n",
    "                    if t - cand[r] < ret:\n",
    "                        ret = t - cand[r]\n",
    "                if r + 1 < n:\n",
    "                    if cand[r + 1] - t < ret:\n",
    "                        ret = cand[r + 1] - t\n",
    "                return\n",
    "            go2(idx + 1, v)\n",
    "            go2(idx + 1, v + s[idx])\n",
    "        go2(0, 0)\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def merge(nums1,nums2):\n",
    "    nums3=[]\n",
    "    i,j=0,0\n",
    "    while(i<=len(nums1)-1 and j<=len(nums2)-1):\n",
    "        if nums1[i]<=nums2[j]:\n",
    "            nums3.append(nums1[i])\n",
    "            i=i+1\n",
    "        else:\n",
    "            nums3.append(nums2[j])\n",
    "            j=j+1\n",
    "    nums3=nums3+nums1[i:]+nums2[j:]\n",
    "    return nums3\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n=len(nums)\n",
    "        n1=n//2\n",
    "        n2=n-n1\n",
    "        nums1=nums[:n1]\n",
    "        nums2=nums[n1:]\n",
    "        ls1=[0]\n",
    "        for i in range(n1):\n",
    "            ls1=merge(ls1,[num+nums1[i] for num in ls1 ])\n",
    "        print(ls1)\n",
    "        ls2=[0]\n",
    "        for i in range(n2):\n",
    "            ls2=merge(ls2,[num+nums2[i] for num in ls2 ])\n",
    "        l=0\n",
    "        r=len(ls2)-1\n",
    "        result=10**10\n",
    "        while(l<len(ls1) and r>-1):\n",
    "            if ls1[l]+ls2[r]==goal:\n",
    "                return 0\n",
    "            elif ls1[l]+ls2[r]>goal:\n",
    "                result=min(result,abs(ls1[l]+ls2[r]-goal))\n",
    "                r-=1\n",
    "            elif ls1[l] + ls2[r] < goal:\n",
    "                result = min(result, abs(ls1[l] + ls2[r] - goal))\n",
    "                l+= 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        # def subset_sum(s, e):\n",
    "        #     a = e - s + 1\n",
    "        #     b = 1 << a\n",
    "        #     sums = [0] * b\n",
    "        #     # print(a, b)\n",
    "        #     for i in range(1, b):\n",
    "        #         for j in range(a-1, -1, -1):\n",
    "        #             t = 1 << j\n",
    "        #             if t & i:\n",
    "        #                 sums[i] = nums[s+j] + sums[i - t]\n",
    "        #                 break\n",
    "            \n",
    "        #     return sums\n",
    "\n",
    "        def subset_sum(arrs):\n",
    "            res = set([0])\n",
    "            for num0 in arrs:\n",
    "                tmp = set()\n",
    "                for num1 in res:\n",
    "                    tmp.add(num0 + num1)\n",
    "                res = res | tmp\n",
    "            \n",
    "            return list(res)\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        # left = subset_sum(0, m)\n",
    "        left = subset_sum(nums[:m])\n",
    "        if goal in set(left):\n",
    "            return 0\n",
    "        # right = subset_sum(m+1, n-1)\n",
    "        right = subset_sum(nums[m:])\n",
    "        if goal in set(right):\n",
    "            return 0\n",
    "        \n",
    "        left.sort()\n",
    "        right.sort()\n",
    "        i = 0\n",
    "        sz = len(left)\n",
    "        j = len(right) - 1\n",
    "\n",
    "        ans = int(1e9)\n",
    "        while i < sz and j >= 0:\n",
    "            t = left[i] + right[j]\n",
    "            ans = min(ans, abs(t-goal))\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "            if t > goal:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        n1 = nums[:n//2+1]\n",
    "        n2 = nums[n//2+1:]\n",
    "        L1,L2 = [],[]\n",
    "        \n",
    "        for i in range(len(n1)+1):\n",
    "            for l in itertools.combinations(n1,i):\n",
    "                L1.append(sum(l))\n",
    "        for i in range(len(n2)+1):\n",
    "            for l in itertools.combinations(n2,i):\n",
    "                L2.append(sum(l))\n",
    "        L1.sort();L2.sort()\n",
    "        l1 = len(L1)\n",
    "        res = inf\n",
    "        for i in L2:\n",
    "            pos = bisect_left(L1,goal-i)\n",
    "            if pos == 0:res = min(res,abs(goal-i-L1[0]))\n",
    "            elif pos == l1:res = min(res,abs(goal-i-L1[-1]))\n",
    "            else:res = min(res,abs(goal-i-L1[pos]),abs(goal-i-L1[pos-1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        h = len(nums)//2\n",
    "        l = set()\n",
    "        for m in range(0,1<<h):\n",
    "            acc = 0\n",
    "            for i in range(h):\n",
    "                if m >> i & 1:\n",
    "                    acc += nums[i]\n",
    "            l.add(acc)\n",
    "        l = list(l)\n",
    "        l.sort()\n",
    "\n",
    "        f = len(nums) - h\n",
    "        ans = inf\n",
    "        r = set()\n",
    "        for m in range(0,1<<f):\n",
    "            acc = 0\n",
    "            for i in range(f):\n",
    "                if m >> i & 1:\n",
    "                    acc += nums[i+h]\n",
    "            r.add(acc)\n",
    "        \n",
    "        for acc in r:\n",
    "            p = bisect_right(l, goal - acc)\n",
    "            if p != len(l):\n",
    "                ans = min(abs(goal - acc - l[p]), ans)\n",
    "            if p - 1 >= 0:\n",
    "                ans = min(abs(goal - acc - l[p-1]),ans)\n",
    "\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def dfs(a,b):\n",
    "            dc = {0}\n",
    "            for i in range(a, b):\n",
    "                v = nums[i]\n",
    "                for x in list(dc):\n",
    "                    dc.add(x+v)\n",
    "            return dc\n",
    "        lis0, lis1 = sorted(dfs(0,n//2)), sorted(dfs(n//2,n), reverse=True)\n",
    "        srt0, srt1, res = len(lis0) - 1, len(lis1) - 1, abs(goal)\n",
    "        while srt0 >= 0 and srt1 >= 0 and res:\n",
    "            v = lis0[srt0] + lis1[srt1] - goal\n",
    "            res = min(res, abs(v))\n",
    "            if v > 0: srt0 -= 1\n",
    "            else: srt1 -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        temp = sorted(nums)\n",
    "        left = temp[:len(temp)// 2]\n",
    "        right = temp[len(temp)// 2:]\n",
    "        def m2(arr):\n",
    "            n = len(arr)\n",
    "            dp = set([0])  \n",
    "            for num in arr:\n",
    "                new_sums = set()\n",
    "                for sum_val in dp:\n",
    "                    new_sums.add(sum_val + num)\n",
    "                dp.update(new_sums)\n",
    "            return sorted(list(dp))\n",
    "        def m1(l1:List[int], l2:List[int],goal:int) -> int:\n",
    "            i = 0\n",
    "            j = len(l2) - 1\n",
    "            result = abs(l1[i] + l2[j] - goal)\n",
    "            while i < len(l1) and j >= 0: \n",
    "                t = l1[i] + l2[j] - goal\n",
    "                if abs(t) < result:\n",
    "                    result = abs(t)\n",
    "                if t > 0:\n",
    "                    j-= 1\n",
    "                elif t < 0:\n",
    "                    i+= 1\n",
    "                else:break\n",
    "            return result\n",
    "        return m1(m2(left),m2(right),goal)\n",
    "        \n",
    "\n",
    "         \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        t=goal\n",
    "        n=len(nums)\n",
    "        t1,t2=[0],[0]\n",
    "        \n",
    "        ans=abs(t)\n",
    "        \n",
    "        for i in range(n//2):\n",
    "            for j in range(len(t1)-1,-1,-1):\n",
    "                t1.append(t1[j]+nums[i])\n",
    "                \n",
    "        for i in range(n//2,n):\n",
    "            for j in range(len(t2)-1,-1,-1):\n",
    "                t2.append(t2[j]+nums[i])\n",
    "                \n",
    "        t2.sort();  #set in python is unordered\n",
    "        s1=set(t1)\n",
    "        for v in s1:\n",
    "            pos=bisect_left(t2,t-v)\n",
    "            if pos<len(t2):\n",
    "                ans=min(ans,abs(t-v-t2[pos]))\n",
    "            if pos>0:\n",
    "                ans=min(ans,abs(t-v-t2[pos-1]))\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def getAllComp(arr: List[int]):\n",
    "            r = set()\n",
    "            for i in range(len(arr) + 1):\n",
    "                r |= {sum(k) for k in itertools.combinations(arr, i)}\n",
    "            return r\n",
    "\n",
    "        l = sorted(getAllComp(nums[:n // 2]))\n",
    "        r = sorted(getAllComp(nums[n // 2:]))\n",
    "\n",
    "        ans = abs(goal)\n",
    "        \n",
    "        for acc in r:\n",
    "            p = bisect_right(l, goal - acc)\n",
    "            if p != len(l):\n",
    "                ans = min(abs(goal - acc - l[p]), ans)\n",
    "            if p - 1 >= 0:\n",
    "                ans = min(abs(goal - acc - l[p-1]),ans)\n",
    "\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import itertools\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # 返回 arr中 0个 到 len(arr)个 的 sum(组合)\n",
    "        def getAllComp(arr: List[int]):\n",
    "            r = set()\n",
    "            for i in range(len(arr) + 1):\n",
    "                r |= {sum(k) for k in itertools.combinations(arr, i)}\n",
    "            return r\n",
    "\n",
    "        left = sorted(getAllComp(nums[:n // 2]))\n",
    "        right = sorted(getAllComp(nums[n // 2:]))\n",
    "\n",
    "        res = abs(goal) # 最大就是 一个都不选的时候。\n",
    "        for num in left:\n",
    "            # 二分找到最接近 goal - num 的位置， 差值最小的就在 前一个，或者该位置。\n",
    "            i = bisect.bisect_left(right, goal - num)\n",
    "            if i == len(right):\n",
    "                res = min(res, abs(right[-1] + num - goal))\n",
    "            elif i == 0:\n",
    "                res = min(res, abs(right[0] + num - goal))\n",
    "            else:\n",
    "                res = min(res, abs(right[i] + num - goal), abs(right[i - 1] + num - goal))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        # 如果直接二进制枚举，会导致乘以一个n的复杂度，现在采用状态压缩进行优化\n",
    "        def work(arr):\n",
    "            m = len(arr)\n",
    "            f = [0] * (1 << m)\n",
    "            for i in range(1, 1 << m):\n",
    "                f[i] = f[i^i&-i] + arr[(i&-i).bit_length()-1]\n",
    "            return sorted(list(set(f)))\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        A, B = work(nums[:m]), work(nums[m:])\n",
    "        ans = inf\n",
    "        for b in B:\n",
    "            l, r = 0, len(A)-1\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if A[mid] + b - goal >= 0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l > 0: ans = min(ans, abs(A[l-1] + b - goal))\n",
    "            ans = min(ans, abs(A[l] + b - goal))\n",
    "            if ans == 0: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        def cal(arr):\n",
    "            m=len(arr)\n",
    "            bit={1<<i:arr[i] for i in range(m)}\n",
    "            dp=[0]*(1<<m)\n",
    "            for i in range(1,1<<m):\n",
    "                dp[i]=dp[i^i&-i]+bit[i&-i]\n",
    "            return sorted(list(set(dp)))\n",
    "\n",
    "        n=len(nums)\n",
    "        a,b=nums[:n//2], nums[n//2:]\n",
    "        A,B=cal(a),cal(b)\n",
    "        N=len(A)\n",
    "        res=inf\n",
    "        for b in B:\n",
    "            # 二分查找\n",
    "            index=bisect_left(A, goal-b)\n",
    "            if index<N:res=min(res,abs(goal-b-A[index]))\n",
    "            if index>0:res=min(res,abs(goal-b-A[index-1]))\n",
    "            if res==0:break\n",
    "        return res\n",
    "\n",
    "        # n = len(nums)\n",
    "        # m = n // 2\n",
    "        # left = []\n",
    "        # for i in range(1 << m):\n",
    "        #     tot = 0\n",
    "        #     k = i\n",
    "        #     while k:\n",
    "        #         lb = k & -k\n",
    "        #         tot += nums[lb.bit_length()-1]\n",
    "        #         k -= lb\n",
    "        #     left.append(tot)\n",
    "        # left = list(set(left))\n",
    "        # left.sort()\n",
    "        # ans = inf\n",
    "        # def min(a, b):\n",
    "        #     if a < b:\n",
    "        #         return a\n",
    "        #     return b\n",
    "        # for i in range(1 << (n - m)):\n",
    "        #     tot = 0\n",
    "        #     for j in range(0, n-m):\n",
    "        #         if i >> j & 1:\n",
    "        #             tot += nums[j + m]\n",
    "        #     l, r = 0, len(left)-1\n",
    "        #     while l < r:\n",
    "        #         mid = (l + r) // 2\n",
    "        #         if left[mid] + tot - goal >= 0:\n",
    "        #             r = mid\n",
    "        #         else:\n",
    "        #             l = mid + 1\n",
    "        #     if l != 0:\n",
    "        #         ans = min(ans, abs(left[l-1] + tot - goal))\n",
    "        #     if l != len(left)-1:\n",
    "        #         ans = min(ans, abs(left[l+1] + tot - goal))\n",
    "        #     ans = min(ans, abs(left[l] + tot - goal))\n",
    "        # return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def state_compress(lst):\n",
    "            m = len(lst)\n",
    "            bit = {1<<i: lst[i] for i in range(m)}\n",
    "            dp=[0]*(1<<m)\n",
    "            for i in range(1, 1<<m):\n",
    "                dp[i]=dp[i^i&-i]+bit[i&-i]\n",
    "            return sorted(list(set(dp)))\n",
    "\n",
    "        pre = state_compress(nums[:n//2])\n",
    "        post = state_compress(nums[n//2:])\n",
    "\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = len(post)-1\n",
    "        while i < len(pre) and j >= 0:\n",
    "            ans = min(ans, abs(goal-pre[i]-post[j]))\n",
    "            if not ans:\n",
    "                return ans\n",
    "            if pre[i]+post[j] > goal:\n",
    "                j -= 1\n",
    "            elif pre[i]+post[j] < goal:\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        # 如果直接二进制枚举，会导致乘以一个n的复杂度，现在采用状态压缩进行优化\n",
    "        def work(arr):\n",
    "            m = len(arr)\n",
    "            f = [0] * (1 << m)\n",
    "            for i in range(1, 1 << m):\n",
    "                f[i] = f[i^i&-i] + arr[(i&-i).bit_length()-1]\n",
    "            return sorted(list(set(f)))\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        A, B = work(nums[:m]), work(nums[m:])\n",
    "        # print(A, B)\n",
    "        ans = inf\n",
    "        for b in B:\n",
    "            l, r = 0, len(A)-1\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if A[mid] + b - goal >= 0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l > 0: ans = min(ans, abs(A[l-1] + b - goal))\n",
    "            ans = min(ans, abs(A[l] + b - goal))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        def work(arr):\n",
    "            m = len(arr)\n",
    "            f = [0] * (1 << m)\n",
    "            for i in range(1, 1 << m):\n",
    "                f[i] = f[i^i&-i] + arr[(i&-i).bit_length()-1]\n",
    "            return sorted(list(set(f)))\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        A, B = work(nums[:m]), work(nums[m:])\n",
    "        ans = inf\n",
    "        for b in B:\n",
    "            l, r = 0, len(A)-1\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if A[mid] + b - goal >= 0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l > 0:\n",
    "                ans = min(ans, abs(A[l-1] + b - goal))\n",
    "            ans = min(ans, abs(A[l] + b - goal))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def state_compress(lst):\n",
    "            m = len(lst)\n",
    "            bit ={1<<i: lst[i] for i in range(m)}\n",
    "            dp = [0]*(1<<m)\n",
    "            for i in range(1,1<<m):\n",
    "                dp[i] = dp[i^i&-i] + bit[i&-i]\n",
    "            return sorted(list(set(dp)))\n",
    "        pre = state_compress(nums[:n//2])\n",
    "        post = state_compress(nums[n//2:])\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = len(post)-1\n",
    "        while i < len(pre) and j >= 0:\n",
    "            ans = min(ans, abs(goal-pre[i]-post[j]))\n",
    "            if not ans:\n",
    "                return ans\n",
    "            if pre[i]+post[j] > goal:\n",
    "                j -= 1\n",
    "            elif pre[i]+post[j] < goal:\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        def subset_sum(s, e):\n",
    "            a = e - s + 1\n",
    "            b = 1 << a\n",
    "            sums = [0] * b\n",
    "            # print(a, b)\n",
    "            for i in range(1, b):\n",
    "                for j in range(a-1, -1, -1):\n",
    "                    t = 1 << j\n",
    "                    if t & i:\n",
    "                        sums[i] = nums[s+j] + sums[i - t]\n",
    "                        break\n",
    "            \n",
    "            return sums\n",
    "\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        left = subset_sum(0, m)\n",
    "        if goal in set(left):\n",
    "            return 0\n",
    "        right = subset_sum(m+1, n-1)\n",
    "        if goal in set(right):\n",
    "            return 0\n",
    "        \n",
    "        left.sort()\n",
    "        right.sort()\n",
    "        i = 0\n",
    "        sz = len(left)\n",
    "        j = len(right) - 1\n",
    "\n",
    "        ans = int(1e9)\n",
    "        while i < sz and j >= 0:\n",
    "            t = left[i] + right[j]\n",
    "            ans = min(ans, abs(t-goal))\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "            if t > goal:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        def work(arr):\n",
    "            m = len(arr)\n",
    "            f = [0] * (1 << m)\n",
    "            for i in range(1, 1 << m):\n",
    "                f[i] = f[i^i&-i] + arr[(i&-i).bit_length()-1]\n",
    "            return sorted(list(set(f)))\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        A, B = work(nums[:m]), work(nums[m:])\n",
    "        res = inf\n",
    "        N = len(A)\n",
    "        for b in B:\n",
    "            index=bisect_left(A,goal-b)\n",
    "            if index<N:res=min(res,abs(goal-b-A[index]))\n",
    "            if index>0:res=min(res,abs(goal-b-A[index-1]))\n",
    "            if res==0:break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def state_compress(lst):\n",
    "            m = len(lst)\n",
    "            bit = {1<<i: lst[i] for i in range(m)}\n",
    "            dp=[0]*(1<<m)\n",
    "            for i in range(1, 1<<m):\n",
    "                dp[i]=dp[i^i&-i]+bit[i&-i]\n",
    "            return sorted(list(set(dp)))\n",
    "\n",
    "        pre = state_compress(nums[:n//2])\n",
    "        post = state_compress(nums[n//2:])\n",
    "\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = len(post)-1\n",
    "        while i < len(pre) and j >= 0:\n",
    "            ans = min(ans, abs(goal-pre[i]-post[j]))\n",
    "            if not ans:\n",
    "                return ans\n",
    "            if pre[i]+post[j] > goal:\n",
    "                j -= 1\n",
    "            elif pre[i]+post[j] < goal:\n",
    "                i += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/closest-subsequence-sum/solutions/1638880/-by-liupengsay-ydb9/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        # 如果直接二进制枚举，会导致乘以一个n的复杂度，现在采用状态压缩进行优化\n",
    "        def work(arr):\n",
    "            m = len(arr)\n",
    "            f = [0] * (1 << m)\n",
    "            for i in range(1, 1 << m):\n",
    "                f[i] = f[i^i&-i] + arr[(i&-i).bit_length()-1]\n",
    "            return sorted(list(set(f)))\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        A, B = work(nums[:m]), work(nums[m:])\n",
    "        # print(A, B)\n",
    "        ans = inf\n",
    "        for b in B:\n",
    "            l, r = 0, len(A)-1\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if A[mid] + b - goal >= 0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l > 0:\n",
    "                ans = min(ans, abs(A[l-1] + b - goal))\n",
    "            if l < len(A) - 1:\n",
    "                ans = min(ans, abs(A[l+1] + b - goal))\n",
    "            ans = min(ans, abs(A[l] + b - goal))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def state_compress(lst):\n",
    "            m = len(lst)\n",
    "            bit = {1 << i: lst[i] for i in range(m)}\n",
    "            dp = [0] * (1 << m)\n",
    "            for i in range(1, 1 << m):\n",
    "                dp[i] = dp[i ^ (i & -i)] + bit[i & -i]\n",
    "            return sorted(list(set(dp)))\n",
    "        pre = state_compress(nums[:n//2])\n",
    "        post = state_compress(nums[n//2:])\n",
    "        ans = inf\n",
    "        i, j = 0, len(post) - 1\n",
    "        while i < len(pre) and j >= 0:\n",
    "            ans = min(ans, abs(goal - pre[i] - post[j]))\n",
    "            if ans == 0:\n",
    "                return ans\n",
    "            if pre[i] + post[j] > goal:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def state_compress(lst):\n",
    "            m = len(lst)\n",
    "            bit = {1<<i: lst[i] for i in range(m)}\n",
    "            dp=[0]*(1<<m)\n",
    "            for i in range(1, 1<<m):\n",
    "                dp[i]=dp[i^i&-i]+bit[i&-i]\n",
    "            return sorted(list(set(dp)))\n",
    "\n",
    "        pre = state_compress(nums[:n//2])\n",
    "        post = state_compress(nums[n//2:])\n",
    "\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = len(post)-1\n",
    "        while i < len(pre) and j >= 0:\n",
    "            ans = min(ans, abs(goal-pre[i]-post[j]))\n",
    "            if not ans:\n",
    "                return ans\n",
    "            if pre[i]+post[j] > goal:\n",
    "                j -= 1\n",
    "            elif pre[i]+post[j] < goal:\n",
    "                i += 1\n",
    "        return ans\n",
    "\n",
    "    # dfs版本\n",
    "    def minAbsDifference2(self, nums: List[int], goal: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "\n",
    "        def check(lst):\n",
    "            m = len(lst)\n",
    "            res = set()\n",
    "            def dfs(pre, i):\n",
    "                if i == m:\n",
    "                    res.add(pre)\n",
    "                    return\n",
    "                dfs(pre, i + 1)\n",
    "                dfs(pre + lst[i], i + 1)\n",
    "                return\n",
    "            dfs(0, 0)\n",
    "            return SortedList(list(res))\n",
    "\n",
    "        n = len(nums)\n",
    "        left = check(nums[:n // 2])\n",
    "        right = check(nums[n // 2:])\n",
    "        a, b = len(left), len(right)\n",
    "\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = b - 1\n",
    "        while i < a and j >= 0:\n",
    "            cur = left[i] + right[j] - goal\n",
    "            if abs(cur)  < ans:\n",
    "                ans = abs(cur)\n",
    "            if cur > 0:\n",
    "                j -= 1\n",
    "            elif cur < 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        # 如果直接二进制枚举，会导致乘以一个n的复杂度，现在采用状态压缩进行优化\n",
    "        def work(arr):\n",
    "            m = len(arr)\n",
    "            f = [0] * (1 << m)\n",
    "            for i in range(1, 1 << m):\n",
    "                f[i] = f[i^i&-i] + arr[(i&-i).bit_length()-1]\n",
    "            return sorted(list(set(f)))\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        A, B = work(nums[:m]), work(nums[m:])\n",
    "        ans = inf\n",
    "        for b in B:\n",
    "            l, r = 0, len(A)-1\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if A[mid] + b - goal >= 0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l > 0: ans = min(ans, abs(A[l-1] + b - goal))\n",
    "            ans = min(ans, abs(A[l] + b - goal))\n",
    "            if ans == 0: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def state_compress(lst):\n",
    "            m = len(lst)\n",
    "            bit = {1<<i: lst[i] for i in range(m)}\n",
    "            dp=[0]*(1<<m)\n",
    "            for i in range(1, 1<<m):\n",
    "                dp[i]=dp[i^i&-i]+bit[i&-i]\n",
    "            return sorted(list(set(dp)))\n",
    "\n",
    "        pre = state_compress(nums[:n//2])\n",
    "        post = state_compress(nums[n//2:])\n",
    "\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = len(post)-1\n",
    "        while i < len(pre) and j >= 0:\n",
    "            ans = min(ans, abs(goal-pre[i]-post[j]))\n",
    "            if not ans:\n",
    "                return ans\n",
    "            if pre[i]+post[j] > goal:\n",
    "                j -= 1\n",
    "            elif pre[i]+post[j] < goal:\n",
    "                i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def state_compress(lst):\n",
    "            m = len(lst)\n",
    "            bit = {1<<i: lst[i] for i in range(m)}\n",
    "            dp=[0]*(1<<m)\n",
    "            for i in range(1, 1<<m):\n",
    "                dp[i]=dp[i^i&-i]+bit[i&-i]\n",
    "            return sorted(list(set(dp)))\n",
    "\n",
    "        pre = state_compress(nums[:n//2])\n",
    "        post = state_compress(nums[n//2:])\n",
    "\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = len(post)-1\n",
    "        while i < len(pre) and j >= 0:\n",
    "            ans = min(ans, abs(goal-pre[i]-post[j]))\n",
    "            if not ans:\n",
    "                return ans\n",
    "            if pre[i]+post[j] > goal:\n",
    "                j -= 1\n",
    "            elif pre[i]+post[j] < goal:\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def state_compress(nums):\n",
    "            n = len(nums)\n",
    "            bit = {1 << i: nums[i] for i in range(n)}\n",
    "            dp = [0] * (1 << n)\n",
    "            for i in range(1, 1 << n):\n",
    "                dp[i] = dp[i ^ i & -i] + bit[i & -i]\n",
    "            return sorted(list(set(dp)))\n",
    "\n",
    "        s1, s2 = state_compress(nums[:n // 2]), state_compress(nums[n // 2:])\n",
    "\n",
    "        ans = abs(goal)\n",
    "        l, r = 0, len(s2) - 1\n",
    "        while ans and l < len(s1) and r >= 0:\n",
    "            t = s1[l] + s2[r]\n",
    "            ans = min(ans, abs(goal - t))\n",
    "            if t > goal:\n",
    "                r -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        # 计算数组不同子集元素和，后排序\n",
    "        def cal(arr):\n",
    "            m=len(arr)\n",
    "            bit={1<<i:arr[i] for i in range(m)}\n",
    "            dp=[0]*(1<<m)\n",
    "            for i in range(1,1<<m):\n",
    "                dp[i]=dp[i^i&-i]+bit[i&-i]\n",
    "            return sorted(list(set(dp)))\n",
    "\n",
    "        n=len(nums)\n",
    "        a,b=nums[:n//2],nums[n//2:]\n",
    "        A,B=cal(a),cal(b)\n",
    "        N=len(A)\n",
    "        res=inf\n",
    "        for b in B:\n",
    "            # 二分查找\n",
    "            index=bisect_left(A,goal-b)\n",
    "            if index<N:res=min(res,abs(goal-b-A[index]))\n",
    "            if index>0:res=min(res,abs(goal-b-A[index-1]))\n",
    "            if res==0:break\n",
    "        return res\n",
    "\n",
    "# 作者：追风少年\n",
    "# 链接：https://leetcode.cn/problems/closest-subsequence-sum/solutions/1292488/python3-zhuang-tai-ya-suo-er-fen-cha-zha-xl7u/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        # 计算数组不同子集元素和，后排序\n",
    "        def cal(arr):\n",
    "            n = len(arr)\n",
    "            bit = {1 << i : arr[i] for i in range(n)} # 字典存储每个数相对位置\n",
    "            dp = [0] * (1 << n) # 用于获取不同位置的数的搭配\n",
    "            for i in range(1, 1 << n):\n",
    "                dp[i] = dp[i - (i & -i)] + bit[i & -i]\n",
    "            return sorted(list(set(dp)))\n",
    "        \n",
    "        n = len(nums)\n",
    "        a, b = nums[:n // 2], nums[n // 2:]\n",
    "        A, B = cal(a), cal(b)\n",
    "        m = len(A)\n",
    "        ans = inf\n",
    "        for b in B:\n",
    "            # 二分查找\n",
    "            idx = bisect_left(A, goal - b)\n",
    "            if idx < m:\n",
    "                ans = min(ans, abs(goal - b - A[idx]))\n",
    "            if idx > 0:\n",
    "                ans = min (ans, abs(goal - b - A[idx - 1]))\n",
    "            if ans == 0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def state_compress(lst):\n",
    "            m = len(lst)\n",
    "            bit = {1<<i: lst[i] for i in range(m)}\n",
    "            dp=[0]*(1<<m)\n",
    "            for i in range(1, 1<<m):\n",
    "                dp[i]=dp[i^i&-i]+bit[i&-i]\n",
    "            return sorted(list(set(dp)))\n",
    "\n",
    "        pre = state_compress(nums[:n//2])\n",
    "        post = state_compress(nums[n//2:])\n",
    "\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = len(post)-1\n",
    "        while i < len(pre) and j >= 0:\n",
    "            ans = min(ans, abs(goal-pre[i]-post[j]))\n",
    "            if not ans:\n",
    "                return ans\n",
    "            if pre[i]+post[j] > goal:\n",
    "                j -= 1\n",
    "            elif pre[i]+post[j] < goal:\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        def state_compress(lst):\n",
    "            m = len(lst)\n",
    "            bit = {1<<i: lst[i] for i in range(m)}\n",
    "            dp=[0]*(1<<m)\n",
    "            for i in range(1, 1<<m):\n",
    "                dp[i]=dp[i^i&-i]+bit[i&-i]\n",
    "            return sorted(list(set(dp)))\n",
    "\n",
    "        pre = state_compress(nums[:n//2])\n",
    "        post = state_compress(nums[n//2:])\n",
    "\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = len(post)-1\n",
    "        while i < len(pre) and j >= 0:\n",
    "            ans = min(ans, abs(goal-pre[i]-post[j]))\n",
    "            if not ans:\n",
    "                return ans\n",
    "            if pre[i]+post[j] > goal:\n",
    "                j -= 1\n",
    "            elif pre[i]+post[j] < goal:\n",
    "                i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        pre = nums[:n // 2]\n",
    "        after = nums[n // 2:]\n",
    "\n",
    "        def get_all(arr):\n",
    "            res = []\n",
    "            m = len(arr)\n",
    "            for i in range(1 << m):\n",
    "                cur = 0\n",
    "                for j in range(m):\n",
    "                    if i & 1 << j:\n",
    "                        cur += arr[j]\n",
    "                res.append(cur)\n",
    "            return list(set(res))\n",
    "\n",
    "        pret = get_all(pre)\n",
    "        aftert = get_all(after)\n",
    "        pret.sort()\n",
    "        aftert.sort()\n",
    "        j = len(aftert) - 1\n",
    "        ans = abs(goal)\n",
    "        # print(pret, aftert)\n",
    "        for i in range(len(pret)):\n",
    "            while j >= 0 and pret[i] + aftert[j] >= goal:\n",
    "                ans = min(ans, abs(pret[i] + aftert[j] - goal))\n",
    "                if ans == 0:\n",
    "                    return ans\n",
    "                j -= 1\n",
    "            if j >= 0:\n",
    "                ans = min(ans, abs(pret[i] + aftert[j] - goal))\n",
    "            if ans == 0:\n",
    "                return ans\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        def get_sums_from_half(half_nums):\n",
    "            l = len(half_nums)\n",
    "            total = pow(2,l)\n",
    "            res = [0] * total\n",
    "            for i in range(total):\n",
    "                for j in range(l):\n",
    "                    if 1<<j & i ==0:\n",
    "                        res[i] =res[i-(1<<j)] +  half_nums[j]\n",
    "                        break\n",
    "            return res\n",
    "\n",
    "        split_index = len(nums)//2\n",
    "        sum1,sum2 = get_sums_from_half(nums[:split_index]),get_sums_from_half(nums[split_index:])\n",
    "        res = 10 **10\n",
    "        for s in sum1:\n",
    "            res = min(res,abs(goal-s))\n",
    "        for s in sum2:\n",
    "            res = min(res,abs(goal-s))\n",
    "        sum1 = list(set(sum1))\n",
    "        sum2 = list(set(sum2))\n",
    "        sum1.sort()\n",
    "        sum2.sort()\n",
    "        l1,l2 = len(sum1),len(sum2)\n",
    "        start = 0\n",
    "        end = len(sum2)-1\n",
    "        while start < l1 and end >=0:\n",
    "            if sum1[start]+sum2[end]-goal == 0: return 0\n",
    "            elif sum1[start]+sum2[end]-goal > 0:\n",
    "                end -= 1\n",
    "            else:\n",
    "                start += 1\n",
    "            if start<l1 and end>=0:\n",
    "                res = min(res,abs(sum1[start]+sum2[end]-goal))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        temp = sorted(nums)\n",
    "        left = temp[:len(temp)// 2]\n",
    "        right = temp[len(temp)// 2:]\n",
    "        def m2(arr):\n",
    "            n = len(arr)\n",
    "            sums = [0]\n",
    "            for num in arr:\n",
    "                new_sums = [num + s for s in sums]  #\n",
    "                sums.extend(new_sums) \n",
    "            return sorted(list(set(sums))) \n",
    "\n",
    "        def m1(l1:List[int], l2:List[int],goal:int) -> int:\n",
    "            i = 0\n",
    "            j = len(l2) - 1\n",
    "            result = abs(l1[i] + l2[j] - goal)\n",
    "            while i < len(l1) and j >= 0: \n",
    "                t = l1[i] + l2[j] - goal\n",
    "                if abs(t) < result:\n",
    "                    result = abs(t)\n",
    "                if t > 0:\n",
    "                    j-= 1\n",
    "                elif t < 0:\n",
    "                    i+= 1\n",
    "                else:break\n",
    "            return result\n",
    "        return m1(m2(left),m2(right),goal)\n",
    "        \n",
    "\n",
    "         \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return min(abs(goal), abs(nums[0] - goal))\n",
    "\n",
    "        def f(L):\n",
    "            vis = set([0])\n",
    "            for i in L:\n",
    "                vis |= {i + b for b in vis}\n",
    "            return vis\n",
    "\n",
    "        left, right = f(nums[: n // 2]), f(nums[n // 2: ])\n",
    "        right = sorted(right)\n",
    "        \n",
    "        ans = 10 ** 18\n",
    "        for i in left:\n",
    "            if goal - i <= right[0]:\n",
    "                ans = min(ans, right[0] - goal + i)\n",
    "            elif goal - i >= right[-1]:\n",
    "                ans = min(ans, goal - i - right[-1])\n",
    "            else:\n",
    "                idx = bisect_left(right, goal - i)\n",
    "                ans = min(ans, goal - i - right[idx - 1], right[idx] - goal + i)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        left, right = nums[:len(nums)//2], nums[len(nums)//2:]\n",
    "        left_res, right_res, res = set(), set(), abs(goal)\n",
    "        for binary in itertools.product([0, 1], repeat = len(left)):\n",
    "            left_res.add(sum([i*j for i, j in zip(binary, left)]))\n",
    "        for binary in itertools.product([0, 1], repeat = len(right)):\n",
    "            right_res.add(sum([i*j for i, j in zip(binary, right)]))\n",
    "        left_res = sorted(left_res)\n",
    "        right_res = sorted(right_res)\n",
    "        for i in right_res:\n",
    "            p = bisect.bisect(left_res, goal-i)\n",
    "            if 0<=p<len(left_res): res = min(abs(i+left_res[p]-goal), res)\n",
    "            if p<len(left_res)-1: res = min(abs(i+left_res[p+1]-goal), res)\n",
    "            if p>0: res = min(abs(i+left_res[p-1]-goal), res)       \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        left, right = nums[:len(nums)//2], nums[len(nums)//2:]\n",
    "        left_res, right_res, res = set(), set(), abs(goal)\n",
    "        for binary in itertools.product([0, 1], repeat = len(left)):\n",
    "            left_res.add(sum([i*j for i, j in zip(binary, left)]))\n",
    "        for binary in itertools.product([0, 1], repeat = len(right)):\n",
    "            right_res.add(sum([i*j for i, j in zip(binary, right)]))\n",
    "        left_res = sorted(left_res)\n",
    "        for i in right_res:\n",
    "            p = bisect.bisect(left_res, goal-i)\n",
    "            if 0<=p<len(left_res): res = min(abs(i+left_res[p]-goal), res)\n",
    "            #if p<len(left_res)-1: res = min(abs(i+left_res[p+1]-goal), res)\n",
    "            if p>0: res = min(abs(i+left_res[p-1]-goal), res)       \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        def subset_sum(s, e):\n",
    "            a = e - s + 1\n",
    "            b = 1 << a\n",
    "            sums = [0] * b\n",
    "            # print(a, b)\n",
    "            for i in range(1, b):\n",
    "                for j in range(a-1, -1, -1):\n",
    "                    t = 1 << j\n",
    "                    if t & i:\n",
    "                        sums[i] = nums[s+j] + sums[i - t]\n",
    "                        break\n",
    "            \n",
    "            return sums\n",
    "\n",
    "        n = len(nums)\n",
    "        m = n // 2\n",
    "        left = subset_sum(0, m)\n",
    "        right = subset_sum(m+1, n-1)\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        left_st = set(left)\n",
    "        right_st = set(right)\n",
    "        if goal in left_st or goal in right_st:\n",
    "            return 0\n",
    "        \n",
    "        left.sort()\n",
    "        right.sort()\n",
    "        i = 0\n",
    "        sz = len(left)\n",
    "        j = len(right) - 1\n",
    "\n",
    "        ans = int(1e9)\n",
    "        while i < sz and j >= 0:\n",
    "            t = left[i] + right[j]\n",
    "            ans = min(ans, abs(t-goal))\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "            if t > goal:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        # pass nums into 2 part\n",
    "        # nlogn (n=1e6)\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        def f(a):\n",
    "            s = set()\n",
    "            for x in a:\n",
    "                dont = s.copy()\n",
    "                for y in s:\n",
    "                    dont.add(x + y)\n",
    "                dont.add(x)\n",
    "                s = dont\n",
    "            return s\n",
    "\n",
    "        half = n >> 1\n",
    "        left = f(nums[:half])\n",
    "        right = f(nums[half:])\n",
    "\n",
    "        left = sorted(left)\n",
    "        right = sorted(right)\n",
    "        n = len(right)\n",
    "\n",
    "        res = min(abs(goal), abs(goal - right[0]), abs(goal - right[-1]))\n",
    "        if left:\n",
    "            res = min(res, abs(goal - left[0]), abs(goal - left[-1]))\n",
    "\n",
    "        for x in left:\n",
    "            target = goal - x\n",
    "            j = bisect_left(right, target)\n",
    "            if j == n or j == 0:\n",
    "                res = min(res, abs(target))\n",
    "            if j < n:\n",
    "                res = min(res, abs(right[j] - target))\n",
    "            if j > 0:\n",
    "                res = min(res, abs(right[j - 1] - target))\n",
    "\n",
    "            if res == 0:\n",
    "                return res\n",
    "        # print(left, right)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        def check(lst):\n",
    "            m = len(lst)\n",
    "            res = set()\n",
    "            def dfs(pre, i):\n",
    "                if i == m:\n",
    "                    res.add(pre)\n",
    "                    return\n",
    "                dfs(pre, i + 1)\n",
    "                dfs(pre + lst[i], i + 1)\n",
    "                return \n",
    "            dfs(0, 0)\n",
    "            return SortedList(list(res))\n",
    "        n = len(nums)\n",
    "        left = check(nums[:n // 2])\n",
    "        right = check(nums[n // 2:])\n",
    "        a, b = len(left), len(right)\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = b - 1\n",
    "        while i < a and j >= 0:\n",
    "            cur = left[i] + right[j] - goal\n",
    "            if abs(cur) < ans:\n",
    "                ans = abs(cur)\n",
    "            if cur > 0:\n",
    "                j -= 1\n",
    "            elif cur < 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "\n",
    "        def check(lst):\n",
    "            m = len(lst)\n",
    "            res = set()\n",
    "            def dfs(pre, i):\n",
    "                if i == m:\n",
    "                    res.add(pre)\n",
    "                    return\n",
    "                dfs(pre, i + 1)\n",
    "                dfs(pre + lst[i], i + 1)\n",
    "                return\n",
    "            dfs(0, 0)\n",
    "            return SortedList(list(res))\n",
    "\n",
    "        n = len(nums)\n",
    "        left = check(nums[:n // 2])\n",
    "        right = check(nums[n // 2:])\n",
    "        a, b = len(left), len(right)\n",
    "\n",
    "        ans = abs(goal)\n",
    "        i = 0\n",
    "        j = b - 1\n",
    "        while i < a and j >= 0:\n",
    "            cur = left[i] + right[j] - goal\n",
    "            if abs(cur)  < ans:\n",
    "                ans = abs(cur)\n",
    "            if cur > 0:\n",
    "                j -= 1\n",
    "            elif cur < 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/closest-subsequence-sum/solutions/1638880/-by-liupengsay-ydb9/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return min(abs(goal), abs(nums[0] - goal))\n",
    "\n",
    "        def f(L):\n",
    "            vis = set([0])\n",
    "            vis.add(L[0])\n",
    "            for i in range(1, len(L)):\n",
    "                tmp = set()\n",
    "                for j in vis:\n",
    "                    tmp.add(j + L[i])\n",
    "                for k in tmp:\n",
    "                    vis.add(k)\n",
    "            return vis\n",
    "\n",
    "        left, right = f(nums[: n // 2]), f(nums[n // 2: ])\n",
    "        right = sorted(right)\n",
    "        right = [-inf] + right + [inf]\n",
    "        ans = inf\n",
    "        for i in left:\n",
    "            # if goal - i <= right[0]:\n",
    "            #     ans = min(ans, right[0] - goal + i)\n",
    "            # elif goal - i >= right[-1]:\n",
    "            #     ans = min(ans, goal - i - right[-1])\n",
    "            # else:\n",
    "            idx = bisect_left(right, goal - i)\n",
    "            ans = min(ans, goal - i - right[idx - 1], right[idx] - goal + i)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return min(abs(goal), abs(nums[0] - goal))\n",
    "\n",
    "        def f(L):\n",
    "            vis = set([0])\n",
    "            vis.add(L[0])\n",
    "            for i in range(1, len(L)):\n",
    "                tmp = set()\n",
    "                for j in vis:\n",
    "                    tmp.add(j + L[i])\n",
    "                for k in tmp:\n",
    "                    vis.add(k)\n",
    "            return vis\n",
    "\n",
    "        left, right = f(nums[: n // 2]), f(nums[n // 2: ])\n",
    "        right = sorted(right)\n",
    "        ans = inf\n",
    "        for i in left:\n",
    "            if goal - i <= right[0]:\n",
    "                ans = min(ans, right[0] - goal + i)\n",
    "            elif goal - i >= right[-1]:\n",
    "                ans = min(ans, goal - i - right[-1])\n",
    "            else:\n",
    "                idx = bisect_left(right, goal - i)\n",
    "                ans = min(ans, goal - i - right[idx - 1], right[idx] - goal + i)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsDifference(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return min(abs(goal), abs(nums[0] - goal))\n",
    "\n",
    "        def f(L):\n",
    "            vis = set([0])\n",
    "            vis.add(L[0])\n",
    "            for i in range(1, len(L)):\n",
    "                tmp = set()\n",
    "                for j in vis:\n",
    "                    tmp.add(j + L[i])\n",
    "                for k in tmp:\n",
    "                    vis.add(k)\n",
    "            return vis\n",
    "\n",
    "        left, right = f(nums[: n // 2]), f(nums[n // 2: ])\n",
    "        right = sorted(right)\n",
    "        right = [-10 ** 18] + right + [10 ** 18]\n",
    "        ans = 10 ** 18\n",
    "        for i in left:\n",
    "            # if goal - i <= right[0]:\n",
    "            #     ans = min(ans, right[0] - goal + i)\n",
    "            # elif goal - i >= right[-1]:\n",
    "            #     ans = min(ans, goal - i - right[-1])\n",
    "            # else:\n",
    "            idx = bisect_left(right, goal - i)\n",
    "            ans = min(ans, goal - i - right[idx - 1], right[idx] - goal + i)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minAbsDifference(self, nums, goal):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type goal: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return min(abs(nums[0] - goal), abs(goal))\n",
    "        \n",
    "        cut_pos = n // 2\n",
    "        left_sum = set([0])\n",
    "        for num in nums[:cut_pos]:\n",
    "            left_sum = left_sum.union(set([x + num for x in left_sum]))\n",
    "        \n",
    "        right_sum = set([0])\n",
    "        for num in nums[cut_pos:]:\n",
    "            right_sum = right_sum.union(set([x + num for x in right_sum]))\n",
    "        \n",
    "        left_list = sorted(left_sum)\n",
    "        right_list = sorted(right_sum)\n",
    "\n",
    "        p = len(right_list) - 1\n",
    "        res = abs(goal)\n",
    "        for num in left_list:\n",
    "            while p >= 0 and num + right_list[p] > goal:\n",
    "                p -= 1\n",
    "            \n",
    "            if p >= 0:\n",
    "                res = min(res, abs(num + right_list[p] - goal))\n",
    "            if p < len(right_list) - 1:\n",
    "                res = min(res, abs(num + right_list[p + 1] - goal))\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
